#
# @lc app=leetcode.cn id=40 lang=python
#
# [40] 组合总和 II
#

# @lc code=start
# ## nums[i]!=nums[i-1]法
# class Solution(object):
#     def combinationSum2(self, candidates, target):
#         """
#         :type candidates: List[int]
#         :type target: int
#         :rtype: List[List[int]]
#         """
#         self.candidates = candidates
#         self.candidates.sort()
#         self.target = target
#         self.result = []
#         self.result_item = []
#         self.total = 0
#         self.loop(0)
#         return self.result
        

#     def loop(self, index):
#         if self.total == self.target:
#             self.result.append(self.result_item[:])
#             return
#         if self.total > self.target:
#             return

#         for i in range(index, len(self.candidates)):
#             if i > index:
#                 if self.candidates[i] == self.candidates[i-1]:
#                     continue
#             self.result_item.append(self.candidates[i])
#             self.total += self.candidates[i]
#             self.loop(i+1)
#             self.result_item.pop()
#             self.total -= self.candidates[i]


class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        self.candidates = candidates
        self.candidates.sort()
        self.target = target
        self.result = []
        self.result_item = []
        self.total = 0
        self.loop(0)
        return self.result  

    def loop(self, index):
        if self.total == self.target:
            self.result.append(self.result_item[:])
            return
        if self.total > self.target:
            return

        cset = set()
        for i in range(index, len(self.candidates)):
            if self.candidates[i] in cset:
                continue
            cset.add(self.candidates[i])
            self.result_item.append(self.candidates[i])
            self.total += self.candidates[i]
            self.loop(i+1)
            self.result_item.pop()
            self.total -= self.candidates[i]
        
# @lc code=end

